package cn.lishiyuan.algorithm.tree;


import java.util.Arrays;

public class BTree<T extends Comparable<T>>{

//    private long address; // fd

    private int maxDegree = 3;

    private int size = 0;

    private Node root;

    public BTree(int maxDegree){
        if (maxDegree >= 3 && maxDegree <= 7){
            this.maxDegree = maxDegree;
        }
        size = 0;
        root = null;
    }

    public BTree(){
        this(3);
    }

    private static class Node{
        // 由于需要自底而上合并与删除
        Node parent;
        int degree;
        Object[] keywords;
        // children[0] 小于 key[0] 的所有数据 ，children[1] 大于等于 key[0] 的数据
        Node[] children;
    }

    private static class Leaf extends Node{
        Object[] data;
        /*
         * 叶子节点有前后指针
         */
        private Leaf prev;
        private Leaf next;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean contains(T key) {
        Node node = findNode(key);
        if (node == null){
            return false;
        }

        for (int i = 0; i < node.degree; i++) {
            if(node.keywords[i].equals(key)){
                return true;
            }
        }

        return false;
    }

    public Object find(T key) {
        Leaf node = findNode(key);
        if (node == null){
            return null;
        }
        // 获取index
        for (int i = 0; i < node.degree; i++) {
            if (node.keywords[i].equals(key)) {
                return node.data[i];
            }
        }
        return null;
    }

    public void add(T key,Object data) {
        // 查询叶子节点的可插入位置
        if(key == null){
            return;
        }

        // 寻找合适的位置插入
        if (root==null){
            root = newLeaf(key, data);
            size++;
            return;
        }

        Leaf node = findNode(key);
        if(node !=null ){
            int index = -1;
            for (int i = 0; i < node.degree; i++) {
                // 替换
                if (node.keywords[i].equals(key)) {
                    node.data[i] = data;
                    return;
                }
                if (((T)node.keywords[i]).compareTo(key) > 0) {
                    index = i;
                    break;
                }
            }
            //
            if(index == -1){
                // 所有关键字都小于key，则直接接在最后就行
                index = node.degree;
                node.keywords[index] = key;
                node.data[index] = data;
                node.degree++;
                // 分裂节点，如果需要的话
                divideLeaf(node);
            }else {
                // index 就是目标位置，空出位置
                for (int i = node.degree - 1; i >= index; i--) {
                    node.keywords[i+1] = node.keywords[i];
                    node.data[i+1] = node.data[i];
                }
                node.keywords[index] = key;
                node.data[index] = data;
                node.degree++;

                if(index==0){
                    // 放在第一位，需要修复
                    if(node.parent!=null){
                        for (int i = 0; i <= node.parent.degree; i++) {
                            if(node.parent.children[i].equals(node) && i>0){
                                node.parent.keywords[i-1] = node.keywords[0];
                            }
                        }
                    }
                }

                divideLeaf(node);
            }

            size++;
        }

    }

    public Object remove(T key) {
        // 查询叶子节点的可插入位置
        if(key == null){
            return null;
        }

        // 寻找合适的位置插入
        if (root==null){
            return null;
        }

        Leaf node = findNode(key);
        if(node == null){
            return null;
        }

        int index = -1;

        for (int i = 0; i < node.degree; i++) {
            // 替换
            if (node.keywords[i].equals(key)) {
                index = i;
                break;
            }
        }
        // 不存在节点
        if(index == -1){
            return null;
        }

        // 直接删除不用调整
        if(root == node){
            Object result = node.data[index];
            for (int i = index; i < node.degree-1; i++) {
                // 向前移动一位
                node.keywords[i] = node.keywords[i+1];
                node.data[i]= node.data[i+1];
            }
            node.keywords[node.degree-1] = null;
            node.data[node.degree-1] = null;

            node.degree--;
            size--;

            // 没有节点了就置空
            if(size==0){
                root = null;
            }

            return result;
        }


        // 检查是否需要合并
        double line = Math.ceil(maxDegree / 2.0) - 1;

        // 删除后 依然能保证平衡则直接删除
        if ((node.degree -1) >= line){
            Object result = node.data[index];
            for (int i = index; i < node.degree-1; i++) {
                // 向前移动一位
                node.keywords[i] = node.keywords[i+1];
                node.data[i]= node.data[i+1];
            }
            node.keywords[node.degree-1] = null;
            node.data[node.degree-1] = null;

            node.degree--;

            if (index == 0){
                // 需要调整父级对应节点keyword
                Node parent = node.parent;
                for (int i = 0; i < parent.degree; i++) {
                    if (parent.children[i].equals(node) && i>0) {
                        parent.keywords[i-1] = node.keywords[0];
                        break;
                    }
                }
            }
            size--;
            return result;
        }

        // 无法保持平衡，删除后需要调整平衡状态
        Object result = node.data[index];
        for (int i = index; i < node.degree-1; i++) {
            // 向前移动一位
            node.keywords[i] = node.keywords[i+1];
            node.data[i]= node.data[i+1];
        }

        node.keywords[node.degree-1] = null;
        node.data[node.degree-1] = null;

        node.degree--;

        Leaf left = node.prev;
        Leaf right = node.next;

        if(left != null && left.parent != node.parent){
            left = null;
        }

        if(right != null && right.parent != node.parent){
            right = null;
        }

        mergeLeaf(node,left,right);

        size--;
        return result;
    }

    public void clear() {
        root = null;
        size = 0;
    }

    /**
     * 查找节点
     */
    private Leaf findNode(T key){
        if(key == null){
            return null;
        }
        if(root == null){
            return null;
        }

        Node cur = root;
        while (cur!=null && !(cur instanceof BTree.Leaf)){
            // 查询节点
            for (int i = 0; i < cur.degree; i++) {
                // 第一个大于当前节点的位置
                if(((T)cur.keywords[i]).compareTo(key) > 0){
                    // 前一个节点必然是小于等于key的
                    cur = cur.children[i];
                    break;
                }else if (i == cur.degree - 1) {
                    cur = cur.children[i+1];
                    break;
                }
                // 其他情况直接向后查找i++
            }
        }

        return (Leaf) cur;
    }

    /**
     * 合并叶子
     * @param node
     * @param left
     * @param right
     */
    private void mergeLeaf(Leaf node,Leaf left,Leaf right){

        // 检查是否满足条件
        double line = Math.ceil(maxDegree / 2.0) - 1;
        // 兄弟借元素
        // 先左节点查看
        if(left != null && (left.degree-1) >= line){
            // 借最右边元素
            Object key = left.keywords[left.degree-1];
            Object data= left.data[left.degree-1];
            left.keywords[left.degree-1] = null;
            left.data[left.degree-1] = null;
            left.degree--;

            for (int i = node.degree-1 ;i >= 0; i--) {
                node.data[i+1]= node.data[i];
                node.keywords[i+1] = node.keywords[i];
            }
            node.keywords[0] = key;
            node.data[0] = data;
            node.degree++;

            // 更新父节点的keywords
            Node parent = node.parent;
            for (int i = 0; i <= parent.degree; i++) {
                if (parent.children[i].equals(node)&& i>0) {
                    parent.keywords[i-1] = key;
                    break;
                }
            }

            return;
        }

        // 右节点借元素
        if(right != null && (right.degree-1) >= line){
            // 借最右边元素
            Object key = right.keywords[0];
            Object data= right.data[0];

            // 向前移动
            for (int i = 0 ;i < right.degree-1; i++) {
                right.data[i]= right.data[i+1];
                right.keywords[i] = right.keywords[i+1];
            }
            right.keywords[right.degree-1] = null;
            right.data[right.degree-1] = null;
            right.degree--;

            node.keywords[node.degree] = key;
            node.data[node.degree] = data;
            node.degree++;

            // 处理后一个节点的父节点
            Node parent = right.parent;
            for (int i = 0; i <= parent.degree; i++) {
                if (parent.children[i].equals(right) && i>0) {
                    parent.keywords[i-1] = right.keywords[0];
                    break;
                }
            }

            if(node.degree==1){
                // 如果是第一个元素，则需要第一个大于等于key之前的元素设置过
                parent = node.parent;
                for (int i = 0; i <= parent.degree; i++) {
                    if (parent.children[i].equals(node) && i>0) {
                        parent.keywords[i-1] = key;
                        break;
                    }
                }
            }

            return;

        }


        // 合并兄弟，会导致父节点长度变短导致不符合定义
        // 先合并左兄弟，
        if(left !=null && left.degree > 0){
            // 复制到leaf
            for (int i = 0; i < node.degree; i++) {
                left.keywords[left.degree+i] = node.keywords[i];
                left.data[left.degree+i] = node.data[i];
            }
            left.degree += node.degree;

            left.next = node.next;
            if(node.next!=null){
                node.next.prev = left;
            }


            node.prev = null;
            node.next = null;
            node.parent= null;
            node.keywords= null;
            node.children= null;
            node.data= null;
            node.degree = 0;

            // 父节点删除
            int index = -1;
            Node parent = left.parent;
            for (int i = 0; i <= parent.degree; i++) {
                if(parent.children[i].equals(left)){
                    // 父节点必然是一个node
                    // i开始的所有元素向前移动一位
                    index = i;
                    break;
                }
            }
            if(index!=-1){
                //
                for (int i = index; i < parent.degree-1; i++) {
                    parent.keywords[i] = parent.keywords[i+1];
                }
                for (int i = index+1; i < parent.degree; i++) {
                    parent.children[i] = parent.children[i + 1];
                }
            }

            // 清除多余元素
            parent.keywords[parent.degree-1] = null;
            parent.children[parent.degree] = null;
            parent.degree--;

            // 获取左右兄弟合并父级
            if(parent.degree < line){
                if (parent.parent==null) {
                    // 父节点是根节点
                    if(parent.degree == 0){
                        // 已经只有一个节点了
                        root = left;
                        root.parent = null;
                        parent.children = null;
                        parent.keywords = null;
                        return;
                    }
                }else {
                    // 获取左右节点递归合并
                    int pIndex = -1;
                    for (int i = 0; i <= parent.parent.degree; i++) {
                        if (parent == parent.parent.children[i]) {
                            pIndex = i;
                            break;
                        }
                    }
                    Node pLeft = null;
                    Node pRight = null;
                    if(pIndex-1 >=0){
                        pLeft = parent.parent.children[pIndex-1];
                    }
                    if(pIndex+1 <= parent.parent.degree){
                        pRight = parent.parent.children[pIndex+1];
                    }
                    mergeNode(parent,pLeft, pRight);
                }
            }
            return;
        }

        // 再尝试合并右兄弟
        if(right !=null){
            // 复制到leaf
            for (int i = 0; i < right.degree; i++) {
                node.keywords[node.degree+i] = right.keywords[i];
                node.data[node.degree+i] = right.data[i];
            }
            node.degree += right.degree;

            node.next = right.next;
            if(right.next!=null){
                right.next.prev = node;
            }

            right.prev = null;
            right.next = null;
            right.parent= null;
            right.keywords= null;
            right.children= null;
            right.data= null;
            right.degree = 0;

            // 父节点删除
            int index = -1;
            Node parent = node.parent;
            for (int i = 0; i <= parent.degree; i++) {
                if(parent.children[i].equals(node)){
                    // i-1开始的所有元素向前移动一位
                    index = i;
                    break;
                }
            }
            if(index!=-1){
                for (int i = index; i < parent.degree-1; i++) {
                    parent.keywords[i] = parent.keywords[i+1];
                }
                for (int i = index+1; i < parent.degree; i++) {
                    parent.children[i] = parent.children[i+1];
                }
            }
            // 清除多余元素

            parent.keywords[parent.degree-1] = null;
            parent.children[parent.degree] = null;
            parent.degree--;
            // 获取左右兄弟合并父级
            if(parent.degree < line){
                if (parent.parent==null) {
                    // 当前节点是根节点
                    if(parent.degree == 0){
                        // 已经只有一个节点了
                        root = node;
                        root.parent = null;
                        parent.children = null;
                        parent.keywords = null;
                        return;
                    }
                }else {
                    // 获取左右节点递归合并
                    int pIndex = -1;
                    for (int i = 0; i <= parent.parent.degree; i++) {
                        if (parent == parent.parent.children[i]) {
                            pIndex = i;
                            break;
                        }
                    }
                    Node pLeft = null;
                    Node pRight = null;
                    if(pIndex-1 >=0){
                        pLeft = parent.parent.children[pIndex-1];
                    }
                    if(pIndex+1 <= parent.parent.degree){
                        pRight = parent.parent.children[pIndex+1];
                    }
                    mergeNode(parent,pLeft, pRight);
                }
            }
            return;
        }
    }



    /**
     * 合并节点的情况，这里需要注意的是合并两个node需要一个关键字，需要从父节点下移
     */
    private void mergeNode(Node node,Node left,Node right){

        // 检查是否满足条件
        double line = Math.ceil(maxDegree / 2.0) - 1;
        // 兄弟借元素
        // 先左节点查看
        if(left != null && (left.degree-1) >= line){
            // 借最右边元素
            Object key = left.keywords[left.degree-1];
            Node data= left.children[left.degree];
            left.keywords[left.degree-1] = null;
            left.children[left.degree] = null;
            left.degree--;

            for (int i = node.degree-1 ;i >= 0; i--) {
                node.keywords[i+1] = node.keywords[i];
            }

            for (int i = node.degree ;i >= 0; i--) {
                node.children[i+1]= node.children[i];
            }
            // 更新父节点
            data.parent=node;
            node.keywords[0] = key;
            node.children[0] = data;
            node.degree++;
            // 更新父节点的keywords
            Node parent = node.parent;
            for (int i = 0; i <= parent.degree; i++) {
                if (parent.children[i].equals(node) && i>0) {
                    parent.keywords[i-1] = key;
                    break;
                }
            }
            return;
        }

        // 先右节点借元素
        if(right != null && (right.degree-1) >= line){
            // 借最右边元素
            Object key = right.keywords[0];
            Node data= right.children[0];

            for (int i = 0 ;i < right.degree-1; i++) {
                right.keywords[i] = right.keywords[i+1];
            }
            for (int i = 0 ;i < right.degree; i++) {
                right.children[i]= right.children[i+1];
            }
            right.keywords[right.degree-1] = null;
            right.children[right.degree] = null;
            right.degree--;

            // 更新父节点
            data.parent=node;
            node.keywords[node.degree] = key;
            node.children[node.degree+1] = data;
            node.degree++;

            // 处理后一个节点的父节点
            Node parent = right.parent;
            for (int i = 0; i <= parent.degree; i++) {
                if (parent.children[i].equals(right) && i>0) {
                    parent.keywords[i-1] = right.keywords[0];
                    break;
                }
            }

            if(node.degree==1){
                // 如果是第一个元素，则需要第一个大于等于key之前的元素设置过
                parent = node.parent;
                for (int i = 0; i <= parent.degree; i++) {
                    if (parent.children[i].equals(node) && i>0) {
                        parent.keywords[i-1] = key;
                        break;
                    }
                }
            }
            return;

        }


        // 合并兄弟，会导致父节点长度变短导致不符合定义
        // 先合并左兄弟，
        if(left !=null){
            // 合并node
            // 父节点删除
            int index = -1;
            Node parent = left.parent;
            for (int i = 0; i <= parent.degree; i++) {
                if(parent.children[i].equals(left)){
                    // i-1开始的所有元素向前移动一位
                    index = i;
                    break;
                }
            }
            // 获取分割键并下移
            if(index!=-1){
                left.keywords[left.degree] = parent.keywords[index];
                left.degree++;
            }
            // 此时就对齐了
            for (int i = 0; i < node.degree; i++) {
                left.keywords[left.degree+i] = node.keywords[i];
            }
            for (int i = 0; i <= node.degree; i++) {
                Node child = node.children[i];
                child.parent = left;// 更新子节点指针
                left.children[left.degree+i] = child;
            }

            node.parent= null;
            node.keywords=null;
            node.children=null;

            left.degree+=node.degree;

            node.degree = 0;

            // 向前移动
            if(index!=-1){
                for (int i = index; i < parent.degree-1; i++) {
                    parent.keywords[i] = parent.keywords[i+1];
                }
                for (int i = index+1; i < parent.degree; i++) {
                    parent.children[i] = parent.children[i+1];
                }
            }
            // 清除多余元素
            parent.keywords[parent.degree-1] = null;
            parent.children[parent.degree] = null;
            parent.degree--;
            // 获取左右兄弟合并父级
            if(parent.degree < line){
                if (parent.parent==null) {
                    // 当前节点是根节点
                    if(parent.degree == 0){
                        // 已经只有一个节点了
                        root = left;
                        root.parent = null;
                        parent.children = null;
                        parent.keywords = null;
                        return;
                    }
                }else {
                    // 获取左右节点递归合并
                    int pIndex = -1;
                    for (int i = 0; i <= parent.parent.degree; i++) {
                        if (parent == parent.parent.children[i]) {
                            pIndex = i;
                            break;
                        }
                    }
                    Node pLeft = null;
                    Node pRight = null;
                    if(pIndex-1 >=0){
                        pLeft = parent.parent.children[pIndex-1];
                    }
                    if(pIndex+1 <= parent.parent.degree){
                        pRight = parent.parent.children[pIndex+1];
                    }
                    mergeNode(parent,pLeft, pRight);
                }
            }
            return;
        }

        // 再尝试合并右兄弟
        if(right !=null){
            // 合并node

            // 父节点删除
            int index = -1;
            Node parent = node.parent;
            for (int i = 0; i <= parent.degree; i++) {
                if(parent.children[i].equals(node)){
                    // i-1开始的所有元素向前移动一位
                    index = i;
                    break;
                }
            }
            // 下移
            if(index!=-1){
                node.keywords[node.degree]= parent.keywords[index];
                node.degree++;
            }


            // 此时就对齐了
            for (int i = 0; i < right.degree; i++) {
                node.keywords[node.degree+i] = right.keywords[i];
            }
            for (int i = 0; i <= right.degree; i++) {
                Node child = right.children[i];
                child.parent = node;
                node.children[node.degree+i] = child;
            }
            // 合并节点要构建一个中间关键字

            right.parent= null;
            right.keywords=null;
            right.children=null;
            node.degree+=right.degree;

            right.degree = 0;



            if(index!=-1){
                for (int i = index; i < parent.degree-1; i++) {
                    parent.keywords[i] = parent.keywords[i+1];
                }
                for (int i = index+1; i < parent.degree; i++) {
                    parent.children[i] = parent.children[i+1];
                }
            }
            parent.keywords[parent.degree-1] = null;
            parent.children[parent.degree] = null;
            parent.degree--;
            // 获取左右兄弟合并父级
            if(parent.degree < line){
                if (parent.parent==null) {
                    // 当前节点是根节点
                    if(parent.degree == 0){
                        // 已经只有一个节点了
                        root = node;
                        root.parent = null;
                        parent.children = null;
                        parent.keywords = null;
                        return;
                    }
                }else {
                    // 获取左右节点递归合并
                    int pIndex = -1;
                    for (int i = 0; i <= parent.parent.degree; i++) {
                        if (parent == parent.parent.children[i]) {
                            pIndex = i;
                            break;
                        }
                    }
                    Node pLeft = null;
                    Node pRight = null;
                    if(pIndex-1 >=0){
                        pLeft = parent.parent.children[pIndex-1];
                    }
                    if(pIndex+1 <= parent.parent.degree){
                        pRight = parent.parent.children[pIndex+1];
                    }
                    mergeNode(parent,pLeft, pRight);
                }
            }

            return;
        }
    }

    /**
     * 分裂节点
     * @param node
     */
    private void divideNode(Node node){
        if(node == null){
            return;
        }
        // 不需要分裂
        if (node.degree != maxDegree){
            return;
        }
        // 分裂节点
        // 将前面 maxDegree / 2 分裂出去
        // 比如此时有3个关键字，mid就是1，index=0就是左节点，index=2是右节点，index=1是父节点
        int mid = maxDegree / 2;
        // 也就是从mid到node.degree-1 index 是新节点
        // 如果是叶子节点

        Node parent = node.parent;
        // 如果是普通节点
        // 目标位置
        Object pKey = node.keywords[mid];
        Node rightChild = newNode(node,mid);
        // rightChild子节点的父节点修改
        for (int i = 0; i <= rightChild.degree; i++) {
            rightChild.children[i].parent = rightChild;
        }

        if(parent == null){
            // 根节点
            parent = new Node();
            parent.parent = null;
            parent.keywords = new Object[maxDegree];
            parent.degree=1;
            parent.keywords[0] = pKey;
            parent.children = new Node[maxDegree + 1];
            parent.children[0] = node;
            parent.children[1] = rightChild;
            node.parent = parent;
            rightChild.parent = parent;
            root = parent;
        }else {
            // 查找合适的位置插入，然后检查是否要分裂
            int index = -1;
            for (int i = 0; i <= parent.degree; i++) {
                if (parent.children[i].equals(node)) {
                    // 从这个位置腾出位置
                    index = i;
                    break;
                }
            }

            if(index == -1 || index == parent.degree){
                // 直接接在最后一个位置
                parent.keywords[parent.degree] = pKey;
                parent.children[++parent.degree] = rightChild;
            }else {
                // 向后移动腾出位置
                for (int i = parent.degree-1 ; i >= index ; i--) {
                    parent.keywords[i+1] = parent.keywords[i];
                    parent.children[i+2] = parent.children[i+1];
                }
                parent.keywords[index] = pKey;
                parent.children[index+1] = rightChild;
                parent.degree++;
            }
            rightChild.parent = parent;
            node.parent = parent;
            // 如果需要的话分裂父节点
            divideNode(parent);
        }

    }

    /**
     * 分裂叶子
     * @param old
     */
    private void divideLeaf(Leaf old){
        if(old == null){
            return;
        }
        if (old.degree != maxDegree){
            // 修复父节点，在插入位置时首位的情况下需要修复
            return;
        }
        // 分裂节点
        // 将前面 maxDegree / 2 分裂出去
        int mid = maxDegree / 2;
        // 也就是从mid到node.degree-1 index 是新节点
        // 如果是叶子节点

        Node parent = old.parent;
        Node rightChild = newLeaf(old, mid);
        Object pKey = rightChild.keywords[0];

        if(parent == null){
            // 根节点
            parent = new Node();
            parent.parent = null;
            parent.keywords = new Object[maxDegree];
            parent.degree=1;
            parent.keywords[0] = pKey;
            parent.children = new Node[maxDegree + 1];
            parent.children[0] = old;
            parent.children[1] = rightChild;
            old.parent = parent;
            rightChild.parent = parent;
            root = parent;
        }else {
            // 查找合适的位置插入，然后检查是否要分裂
            int index = -1;
            for (int i = 0; i <= parent.degree; i++) {
                if (parent.children[i].equals(old)) {
                    index = i;
                    break;
                }
            }

            if(index == -1 || index == parent.degree){
                // 直接接在最后一个位置
                parent.keywords[parent.degree] = pKey;
                parent.children[++parent.degree] = rightChild;
                rightChild.parent = parent;
                old.parent = parent;
            }else {
                // 腾出位置
                for (int i = parent.degree-1 ; i >= index ; i--) {
                    parent.keywords[i+1] = parent.keywords[i];
                    parent.children[i+2] = parent.children[i+1];
                }
                parent.keywords[index] = pKey;
                parent.children[index+1] = rightChild;
                parent.degree++;
                rightChild.parent = parent;
                old.parent = parent;
            }

        }
        // 如果需要的话分裂父节点
        divideNode(parent);
    }

    private Node newNode(Node old,int startIndex){
        // 需要将index元素提上父级
        Node node = new Node();
        node.keywords= new Object[maxDegree];
        node.children = new Node[maxDegree + 1];
        node.degree = old.degree - (startIndex+1);
        // 比如需要提升的index是1，那么就需要在2分割，
        /*
             0 1 2
            [1,2,3]
            0 1 2 3
         */
        System.arraycopy(old.keywords,startIndex+1,node.keywords,0,node.degree);
        System.arraycopy(old.children,startIndex+1,node.children,0,(node.degree+1));
        // 旧节点清除数据
        int len = old.degree - startIndex;
        Arrays.fill(old.keywords,startIndex,old.degree,null);
        Arrays.fill(old.children,startIndex + 1, old.degree+1,null);
        old.degree = old.degree - (node.degree+1);
        // 构建节点指针
        node.parent = old.parent;
        return node;
    }

    private Leaf newLeaf(T key,Object data){
        Leaf leaf = new Leaf();
        leaf.keywords= new Object[maxDegree];
        leaf.data = new Object[maxDegree];
        leaf.degree = 1;
        leaf.keywords[0] = key;
        leaf.data[0] = data;
        return leaf;
    }

    private Leaf newLeaf(Leaf oldLeaf,int startIndex){
        Leaf leaf = new Leaf();
        leaf.keywords= new Object[maxDegree];
        leaf.data = new Object[maxDegree];
        leaf.degree = oldLeaf.degree - startIndex;
        System.arraycopy(oldLeaf.keywords,startIndex,leaf.keywords,0,leaf.degree);
        System.arraycopy(oldLeaf.data,startIndex,leaf.data,0,leaf.degree);
        // 旧节点清除数据
        Arrays.fill(oldLeaf.keywords,startIndex,oldLeaf.degree,null);
        Arrays.fill(oldLeaf.data,startIndex,oldLeaf.degree,null);
        oldLeaf.degree = oldLeaf.degree - leaf.degree;
        // 构建节点指针
        // 旧节点的下个节点的上个节点是新节点
        if(oldLeaf.next!=null){
            oldLeaf.next.prev = leaf;
        }
        // 新节点的下个节点是旧节点的下个节点
        leaf.next= oldLeaf.next;

        leaf.prev = oldLeaf;
        oldLeaf.next = leaf;

        return leaf;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        if (root==null){
            builder.append("null");
        }else {
            Node current = root;
            while (current!=null && !(current instanceof Leaf)){
                if(current.children != null){
                    current = current.children[0];
                }
            }
            if(current == null){
                builder.append("error null");
            }else {
                Leaf leaf = (Leaf) current;
                while (leaf!=null){
                    for (int i = 0; i < leaf.degree; i++) {
                        builder.append(leaf.keywords[i]).append("=>");
                    }
                    leaf = leaf.next;
                }
            }

        }


        return builder.toString();
    }
}
